Chapter 3. Quantum Fourier Transform and Phase Estimation

In Chapter 2, we learned how to find the ‘global property’ (constant or balanced) of \(f(x)\) using quantum parallelism. However, the true power of quantum computers lies in finding the Periodicity of \(f(x)\), which is the core of Shor’s factorization algorithm that we will learn in Chapter 4.

The most powerful mathematical tool for finding periodicity is the Fourier Transform. In this chapter, we introduce the Quantum Fourier Transform (QFT), which is the quantum version of the classical Fourier Transform. QFT is exponentially faster than its classical counterpart (FFT), and it itself acts as the core engine of a powerful algorithm called Quantum Phase Estimation.

1. Fundamental Concepts

Discrete Fourier Transform (DFT): The classical DFT takes \(N\) data points (signals) \(x_0, \dots, x_{N-1}\) as input and transforms them into \(N\) frequencies (amplitudes) \(y_0, \dots, y_{N-1}\) that compose the signal. \[y_k = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} x_j e^{2\pi i jk / N}\] This transforms information in the ‘time’ domain into information in the ‘frequency’ domain.
Quantum Fourier Transform (QFT): QFT is the quantum version of DFT. It is a unitary transformation that transforms \(N=2^n\) computational basis states into a new basis called the Fourier basis. \[\text{QFT} |x\rangle = \frac{1}{\sqrt{N}}\sum_{y=0}^{N-1} e^{2\pi i xy / N} |y\rangle\]
- Meaning: It transforms a single state \(|x\rangle\) (a ‘tick’ at time ‘x’) into a state where all \(y\) frequency components are superposed.
Efficiency of QFT: Classically, the fastest method for performing DFT on \(N\) points (FFT) requires about \(O(N \log N)\) operations. Since \(N=2^n\), this becomes \(O(n 2^n)\), which is exponential in \(n\). QFT using a quantum circuit can be implemented with only \(O(n^2)\) gates. This is an exponential speedup.
QFT Circuit: QFT is not composed of a single gate, but rather a combination of the Hadamard (H) gate and Controlled-Rotation gates learned in Chapter 1.
- \(R_k\) gate: \(R_k = \begin{pmatrix} 1 & 0 \\ 0 & e^{2\pi i / 2^k} \end{pmatrix}\) (rotation by \(2\pi/2^k\) radians about the Z-axis)
Quantum Phase Estimation (QPE): The most powerful application of QFT. Given a unitary operator \(U\) and its eigenstate \(|\psi\rangle\), it is an algorithm that finds the phase \(\phi\) of the eigenvalue satisfying \(U|\psi\rangle = e^{2\pi i \phi} |\psi\rangle\).
Inverse QFT (QFT\(^\dagger\)): Since QFT is a unitary transformation, its inverse transformation (\(\text{QFT}^\dagger\)) exists. This transforms the Fourier basis (frequency) back into the computational basis (time/value). The phase estimation algorithm uses inverse QFT rather than QFT to read the final answer.

2. Symbols and Key Relations

QFT (Definition): \(N=2^n\) \[\text{QFT}_{N} : |x\rangle \mapsto \frac{1}{\sqrt{N}}\sum_{y=0}^{N-1} \omega_N^{xy} |y\rangle \quad (\text{where, } \omega_N = e^{2\pi i / N})\]
QFT (Circuit Decomposition for Multiplication): The QFT for an \(n\)-qubit state \(|x\rangle = |x_1 x_2 \dots x_n\rangle\) (binary number \(x_j \in \{0, 1\}\)) is beautifully decomposed as follows. (\(0.x_k x_{k+1} \dots\) is a binary fraction) \[\text{QFT}|x\rangle = \frac{1}{\sqrt{2^n}} \left( |0\rangle + e^{2\pi i 0.x_n} |1\rangle \right) \otimes \left( |0\rangle + e^{2\pi i 0.x_{n-1}x_n} |1\rangle \right) \otimes \dots \otimes \left( |0\rangle + e^{2\pi i 0.x_1 x_2 \dots x_n} |1\rangle \right)\]
Core of Phase Estimation (QPE):
- Input: \(n\) counting qubits \(|0\rangle^{\otimes n}\) and an eigenstate \(|\psi\rangle\) of \(U\).
- Intermediate State (After Controlled-U Operation): \(H^{\otimes n}|0\rangle^{\otimes n} |\psi\rangle \to \frac{1}{\sqrt{2^n}}\sum_{k=0}^{2^n-1} |k\rangle |\psi\rangle\) \(\xrightarrow{C-U^{2^k} \text{ Applied}} \frac{1}{\sqrt{2^n}}\sum_{k=0}^{2^n-1} U^k |k\rangle |\psi\rangle = \frac{1}{\sqrt{2^n}}\sum_{k=0}^{2^n-1} (e^{2\pi i \phi})^k |k\rangle |\psi\rangle\) \[= \left( \frac{1}{\sqrt{2^n}}\sum_{k=0}^{2^n-1} e^{2\pi i \phi k} |k\rangle \right) \otimes |\psi\rangle\]
- Final State (After Applying Inverse QFT): Applying \(\text{QFT}^\dagger\) to the counting register of the above intermediate state, \[|\tilde{\phi}\rangle \otimes |\psi\rangle \quad (\text{where, } |\tilde{\phi}\rangle \text{ is an } n\text{-bit approximation of } \phi)\]

3. Easy Examples (Examples with Deeper Insight)

Example 1: Meaning of QFT (n=2, N=4)

Question: QFT transforms to ‘frequency’, what does that mean?
Answer: QFT changes the state on the ‘time axis’ to the state on the ‘frequency axis’.
Scenario: \(N=4\) (\(n=2\)) system, \(\omega = e^{2\pi i / 4} = i\).
- \(|0\rangle \equiv |00\rangle\): “Tick 0”
- \(|1\rangle \equiv |01\rangle\): “Tick 1”
- \(|2\rangle \equiv |10\rangle\): “Tick 2”
- \(|3\rangle \equiv |11\rangle\): “Tick 3”
Calculation: \(\text{QFT}|1\rangle = \frac{1}{\sqrt{4}}\sum_{y=0}^{3} \omega^{1\cdot y} |y\rangle = \frac{1}{2}( \omega^0|0\rangle + \omega^1|1\rangle + \omega^2|2\rangle + \omega^3|3\rangle )\) \(= \frac{1}{2}( |0\rangle + i|1\rangle + i^2|2\rangle + i^3|3\rangle ) = \frac{1}{2}( |0\rangle + i|1\rangle - |2\rangle - i|3\rangle )\)
- 💡 Detailed Explanation (Frequency Encoding):
  
  “Tick 1”(\(|1\rangle\)) state appears to have all frequency 0, 1, 2, 3 components. But look closely at these coefficients \((1, i, -1, -i)\). This means that the phase increases by \(1/4\) (i.e., frequency ‘1’) consistently as \(y=0 \to 3\), from \(0^\circ \to 90^\circ \to 180^\circ \to 270^\circ\). In contrast, \(\text{QFT}|0\rangle = \frac{1}{2}(|0\rangle + |1\rangle + |2\rangle + |3\rangle)\).
  - QFT \(|0\rangle\): Represents frequency 0 (DC component). No phase change occurs.
  - QFT \(|1\rangle\): Represents frequency 1 (1/4 cycle). The phase changes by a factor of \(i\).
  - QFT \(|2\rangle\): Represents frequency 2 (2/4 cycle). The phase changes by a factor of \(-1\).
  - QFT \(|3\rangle\): Represents frequency 3 (3/4 cycle). The phase changes by a factor of \(-i\).
  That is, QFT transforms the computational basis \(|x\rangle\) into a superposition state with phases corresponding to frequency \(x\).

Example 2: QFT Circuit (n=3, \(N=8\))

Scenario: Construct an n=3 qubit QFT circuit. \(R_k\) denotes a \(C-R_{j-k}\) gate between qubits \(j, k\).
Circuit Diagram:

\(|x_1\rangle \longrightarrow [H] \--- [R_2] \--- [R_3] \--- \text{SWAP} \longrightarrow |\tilde{x}_3\rangle\) \(|x_2\rangle \longrightarrow \quad \quad [H] \--- [R_2] \--- \text{SWAP} \longrightarrow |\tilde{x}_2\rangle\) \(|x_3\rangle \longrightarrow \quad \quad \quad \quad [H] \--- \quad \quad \quad \longrightarrow |\tilde{x}_1\rangle\)
💡 Detailed Explanation (How the Circuit Works and \(O(n^2)\) Efficiency):

Read the product decomposition formula (\(\text{QFT}|x\rangle \propto \dots \otimes (|0\rangle + e^{2\pi i 0.x_1 x_2 x_n} |1\rangle)\)) in reverse.
1. Bottom-most qubit (\(|\tilde{x}_1\rangle\) creation): The bottom line should be \(\frac{1}{\sqrt{2}}(|0\rangle + e^{2\pi i 0.x_1 x_2 x_3} |1\rangle)\). (Binary fraction \(0.x_1 x_2 x_3 = x_1/2 + x_2/4 + x_3/8\))
- \(x_1\) is \(R_2\) (\(\pi/2\)) rotation, \(x_2\) is \(R_3\) (\(\pi/4\)) rotation, \(x_3\) is \(R_4\) (\(\pi/8\)) rotation… Oh, this is the last term of the product decomposition formula!
1. Top qubit (\(|\tilde{x}_3\rangle\) creation): The top row should be \(\frac{1}{\sqrt{2}}(|0\rangle + e^{2\pi i 0.x_3} |1\rangle)\).
- Applying the \(H\) gate to \(|x_3\rangle\) results in \(\frac{1}{\sqrt{2}}(|0\rangle + (-1)^{x_3}|1\rangle) = \frac{1}{\sqrt{2}}(|0\rangle + e^{i\pi x_3}|1\rangle) = \frac{1}{\sqrt{2}}(|0\rangle + e^{2\pi i 0.x_3}|1\rangle)\). (binary fraction \(0.x_3 = x_3/2\))
- This is the first term of the product decomposition formula.

Efficiency: Looking at the circuit, the 1st qubit requires \(H\) and \((n-1)\) C-ROT gates, the 2nd qubit requires \(H\) and \((n-2)\) gates, …, the \(n\)th qubit requires only 1 \(H\) gate. The total number of gates is \(n + (n-1) + \dots + 1 = n(n+1)/2\). (excluding SWAP) This is \(O(n^2)\). When \(n=1000\), classical FFT requires \(\approx 1000 \cdot 2^{1000}\) (impossible), but QFT only requires \(\approx 1000^2 / 2 = 500,000\) (very fast) gates.

Example 3: Phase Estimation (QPE) - Finding the Phase of the T Gate

Problem: The \(T\) gate (\(T = \begin{pmatrix} 1 & 0 \\ 0 & e^{i\pi/4} \end{pmatrix}\)) has an eigenstate \(|1\rangle\). Since \(T|1\rangle = e^{i\pi/4}|1\rangle = e^{2\pi i (1/8)}|1\rangle\), \(\phi = 1/8\).
Let’s find \(\phi=1/8\) (binary 0.001) using QPE with \(n=3\) bit precision.
Circuit: Prepare 3 counting qubits \(|000\rangle\) and a target qubit \(|1\rangle\).
Computation (Step-by-step):
1. H Gate: Counting qubits \(\to \frac{1}{\sqrt{8}}\sum_{k=0}^{7} |k\rangle\).
2. Controlled-U Operation:
  - If \(k=1\) (\(|001\rangle\)): Apply \(C-T^{2^0} = C-T^1\) \(\to e^{2\pi i \phi \cdot 1}\) phase
  - If \(k=2\) (\(|010\rangle\)): Apply \(C-T^{2^1} = C-T^2\) \(\to e^{2\pi i \phi \cdot 2}\) phase
  - …
  - If \(k\): \(\to e^{2\pi i \phi k}\) phase
3. Intermediate State: \(\left( \frac{1}{\sqrt{8}}\sum_{k=0}^{7} e^{2\pi i \phi k} |k\rangle \right) \otimes |1\rangle\)
4. Substitute \(\phi = 1/8\): \(\left( \frac{1}{\sqrt{8}}\sum_{k=0}^{7} e^{2\pi i (k/8)} |k\rangle \right) \otimes |1\rangle\)
5. Apply Inverse QFT:
  Consider the QFT definition \(\text{QFT}|x\rangle = \frac{1}{\sqrt{N}}\sum_y e^{2\pi i xy/N} |y\rangle\).
  If \(x=1\), then \(\text{QFT}|1\rangle = \frac{1}{\sqrt{8}}\sum_k e^{2\pi i (k/8)} |k\rangle\).
  This exactly matches the state in step 4!
  Therefore, applying \(\text{QFT}^\dagger\) (inverse transformation) to this state gives:
  \(\text{QFT}^\dagger \left( \frac{1}{\sqrt{8}}\sum_{k=0}^{7} e^{2\pi i (k/8)} |k\rangle \right) = |1\rangle = |001\rangle\)
💡 Detailed Explanation (Measurement):
> Measuring the counting register always yields \(|001\rangle\).
> Interpreting the binary \(001\) as a fraction gives \(0.001_2\), and
> \(0.001_2 = 0 \cdot \frac{1}{2} + 0 \cdot \frac{1}{4} + 1 \cdot \frac{1}{8} = 1/8\).
> We have precisely determined the phase \(\phi=1/8\) of the \(T\) gate using QPE!

4. Practice Problems

QFT (n=2): Calculate the result of \(\text{QFT}|00\rangle\) in the \(n=2\) (N=4) system, and compare it with the \(\text{QFT}|0\rangle\) from Example 1.
QFT (n=2): Calculate \(\text{QFT}|10\rangle\) (i.e., \(\text{QFT}|2\rangle\)).
QFT Circuit (n=2): Draw the 2-qubit QFT circuit (as in Example 2), and count how many total gates are needed (including SWAP).
QPE (S gate): What is the phase \(\phi\) of the \(S\) gate (\(S|1\rangle = i|1\rangle\))? (in the form \(e^{2\pi i \phi}\)) If we use \(n=2\)-bit QPE to find this \(\phi\), what would be the measurement result (in binary)?
QPE (Inaccurate): If \(\phi = 1/3\) and we perform QPE with \(n=3\) bits, predict what the measurement result would be.

5. Explanation

\(\text{QFT}|00\rangle = \text{QFT}|0\rangle = \frac{1}{\sqrt{4}}\sum_{y=0}^{3} e^{2\pi i (0\cdot y) / 4} |y\rangle = \frac{1}{2}\sum |y\rangle = \frac{1}{2}(|00\rangle + |01\rangle + |10\rangle + |11\rangle)\). This is the same as \(\text{QFT}|0\rangle\) in Example 1.
\(\text{QFT}|10\rangle = \text{QFT}|2\rangle = \frac{1}{2}\sum_{y=0}^{3} e^{2\pi i (2y) / 4} |y\rangle = \frac{1}{2}\sum_{y=0}^{3} e^{\pi i y} |y\rangle\)
\(= \frac{1}{2}(|0\rangle + e^{\pi i}|1\rangle + e^{2\pi i}|2\rangle + e^{3\pi i}|3\rangle) = \frac{1}{2}(|0\rangle - |1\rangle + |2\rangle - |3\rangle)\).
Circuit: \(|x_1\rangle \to [H] \to [R_2] \to \text{SWAP}\)
\(|x_2\rangle \to \quad \quad [H] \to \text{SWAP}\)
A total of 4 gates (2 H, 1 \(C-R_2\), 1 SWAP) are needed.
\(S|1\rangle = i|1\rangle = e^{i\pi/2}|1\rangle = e^{2\pi i (1/4)}|1\rangle\). Therefore, \(\phi = 1/4\).
When encoded with \(n=2\) bits, \(\phi = 0.01_2\) (\(0 \cdot \frac{1}{2} + 1 \cdot \frac{1}{4} = 1/4\)).
The measurement result is \(|01\rangle\).
\(\phi = 1/3 \approx 0.010101\dots_2\). When measured with \(n=3\) bits, the result probabilistically gives values near \(0.010_2 (= 2/8 = 1/4)\) or \(0.011_2 (= 3/8)\). Since \(\phi\) cannot be exactly represented as an \(n\)-bit binary number, the measurement result shows a probability distribution around the binary values closest to \(\phi\).